package com.banding.LeetCode;

public class Practice053 {
    public static int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);

    }

    public static int maxSubArray(int[] nums, int start, int end) {
        if (start == end) {
            return nums[start];
        }

        int mid = (start + end) / 2;

        int leftMax = maxSubArray(nums, start, mid);
        int rightMax = maxSubArray(nums, mid + 1, end);
        int crossMax = getCrossMax(nums, start, mid, end);

        return Math.max(Math.max(leftMax, rightMax), crossMax);

    }

    private static int getCrossMax(int[] nums, int start, int mid, int end) {
        int leftSum = 0;
        int leftSumMax = Integer.MIN_VALUE;
        for (int i = mid; i >= start; i--) {
            leftSum += nums[i];
            leftSumMax = Math.max(leftSum, leftSumMax);
        }

        int rightSum = 0;
        int rightSumMax = Integer.MIN_VALUE;
        for (int i = mid + 1; i <= end; i++) {
            rightSum += nums[i];
            rightSumMax = Math.max(rightSum, rightSumMax);
        }

        return leftSumMax + rightSumMax;

    }


}
